package com.peng.leetcode.bfs;

import java.util.*;

/**
 * CalculateMinimumHP
 * 174. 地下城游戏
 * <p>
 * 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
 * <p>
 * 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
 * <p>
 * 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
 * <p>
 * 为了尽快到达公主，骑士决定每次只向右或向下移动一步。
 * <p>
 * 链接：https://leetcode-cn.com/problems/dungeon-game
 *
 * @author: lupeng6
 * @create: 2021/1/19 17:15
 */
public class CalculateMinimumHP {

    public static void main(String[] args) {
//        int[][] dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
//        int[][] dungeon = {{3, 0, -3}, {-3, -2, -2}, {3, 1, -3}};
//        int[][] dungeon = {{3, -20, 30}, {-3, 4, 0}};
//        int[][] dungeon = {{1, -3, 2}, {0, -1, 2}, {0, 0, -2}};
        int[][] dungeon = {{0, 0, 0}, {-1, 0, 0}, {2, 0, -2}};
//        int[][] dungeon = {{0, -5}, {0, 0}};
        System.out.println(new CalculateMinimumHP().calculateMinimumHP(dungeon));
    }


    /**
     * 广度优先遍历
     *
     * @author lupeng6
     * @date 2021/1/19 17:16
     */
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon.length == 0) {
            return 0;
        }

        this.rows = dungeon.length;
        this.cols = dungeon[0].length;
        this.visited = new int[rows][cols];
        this.marked = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                visited[i][j] = -1;
                marked[i][j] = 0;
            }
        }

        TreeSet<Step> result = new TreeSet<>(new Comparator<Step>() {
            @Override
            public int compare(Step o1, Step o2) {
                return Integer.compare(o1.needMaxLife, o2.needMaxLife);
            }
        });

        Queue<Step> queue = new LinkedList<>();
        int startLife = dungeon[0][0];
        int startNeedLife = startLife < 0 ? -startLife : 0;
        Step start = new Step(0, 0, startLife, startNeedLife);
        start.path = String.format("%s,%s", 0, 0);
        queue.offer(start);
        while (!queue.isEmpty()) {
            Step step = queue.poll();
            int x = step.x;
            int y = step.y;
            int life = step.life;
            if (x == rows - 1 && y == cols - 1) {
                result.add(step);
                continue;
            }
            // 当前点没有访问过 或者 当前的生命值大于访问过的
            if (visited[x][y] == -1 || visited[x][y] <= life || marked[x][y] >= step.needMaxLife) {
                visited[x][y] = life;
                marked[x][y] = step.needMaxLife;

                for (int[] operate : operates) {
                    int newX = x + operate[0];
                    int newY = y + operate[1];
                    int currNeedMaxLife = step.needMaxLife;
                    if (isArea(newX, newY)) {
                        int nextConsumeLife = dungeon[newX][newY];
                        int nextLife = life + nextConsumeLife;
                        int nextNeedMaxLife = Math.max(currNeedMaxLife, -(life + nextConsumeLife));

                        Step next = new Step(newX, newY, nextLife, nextNeedMaxLife);
                        next.path = step.path + String.format(":%s,%s", newX, newY);
                        queue.offer(next);
                    }
                }
            }

        }

        for (Step step : result) {
            return step.needMaxLife + 1;
        }
        return 0;
    }

    // 向下, 向右
    private int[][] operates = {{0, 1}, {1, 0}};

    private int rows;

    private int[][] visited;

    private int[][] marked;

    private int cols;

    private boolean isArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

    static class Step {
        int x;
        int y;
        int life;
        int needMaxLife;

        String path = "";

        public Step(int x, int y, int life, int needMaxLife) {
            this.x = x;
            this.y = y;
            this.life = life;
            this.needMaxLife = needMaxLife;
        }
    }

}
